package pers.sloera.leetcode.editor.cn;

import java.util.Arrays;

/**
 * 摆动排序 II
 * user sloera
 * date 2022-06-28 22:11:17
 */
class WiggleSortIi {
    public static void main(String[] args) {
        Solution solution = new WiggleSortIi().new Solution();
        // int[] nums = {1, 5, 1, 1, 6, 4};
        // 1 2 2:
        // 1 1 2:
        // int[] nums = {1, 3, 2, 2, 3, 1};
        // 1 1 1 1 2 2
        // 3 3 3 3 3 4 4
        int[] nums = {1, 1, 2};
        // nums[step] = nums[step - 1]
        // int[] nums = {1, 2, 2};
        // int[] nums = {1, 2, 2, 3};
        // int[] nums = {1, 2, 2, 3, 3};
        // int[] nums = {1, 4, 3, 4, 1, 2, 1, 3, 1, 3, 2, 3, 3};
        solution.wiggleSort(nums);
        System.out.println(nums);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 因为本身就有一定的顺序性，先从小到大排序
         * 拆分来看，把右侧的有序数组推入左侧，便可以满足要求
         *
         * @param nums 输入
         * @date 2022/6/29
         */
        public void wiggleSort(int[] nums) {
            Arrays.sort(nums);
            int[] copyOfNum = Arrays.copyOf(nums, nums.length);
            // 相同的数，不能超过一半
            int step = (nums.length + 1) >> 1;
            // 111234 121134 121314
            // 0,1 nums[3]  2,3 nums[4]  4,5 nums[5]
            // 把右面的递增插入到左边。那就存在一个问题：如果正好右侧的第一个插入左侧后两个相等，相当于没有交换，所以需要单独处理
            // 此处插入在前面，使用倒序就正好符合要求
            // int[] nums = {1, 2, 2}; 无结果
            // int[] nums = {1, 2, 2, 3};
            if (nums.length % 2 == 0) {
                // 在左侧插入后要反转，所以直接倒序
                for (int right = nums.length - 1, copyOfLeft = 0; right >= 0; right = right - 2, copyOfLeft++) {
                    // 奇数的时候，右边比左边少一个数，可能越界
                    if (copyOfLeft + step < nums.length) {
                        nums[right] = copyOfNum[copyOfLeft + step];
                        nums[right - 1] = copyOfNum[copyOfLeft];
                    } else {
                        nums[right] = copyOfNum[copyOfLeft];
                    }
                }
                return;
            }
            // 不可能碰到右边的数插入左边和右侧相同。比如122，是没有结果的
            for (int left = 0, copyOfLeft = 0; left < nums.length; left = left + 2, copyOfLeft++) {
                nums[left] = copyOfNum[copyOfLeft];
                // 奇数的时候，右边比左边少一个数，可能越界
                if (left + 1 < nums.length) {
                    nums[left + 1] = copyOfNum[copyOfLeft + step];
                }
            }
            System.out.println();
        }
    }

    class Solution1 {
        public void wiggleSort(int[] nums) {
            Arrays.sort(nums);
            int left = 0;
            boolean isLesser = true;
            // 处理所有的数据
            while (left < nums.length) {
                int right = left;
                if (right >= nums.length - 1) {
                    return;
                }
                if (isLesser && nums[left] >= nums[++right]) { // 小于号
                    // 找到第一个大于此数的 排序后，可能存在相等的情况
                    if (nums[left] > nums[right]) {
                        swapTwoNum(nums, left++, right);
                        isLesser = !isLesser;
                        continue;
                    }
                    while (nums[left] == nums[right]) {
                        right++;
                    }
                    isLesser = false;
                } else if (!isLesser && nums[left] <= nums[++right]) { // 大于号
                    // 找到第一个小于此数的 排序后，可能存在相等的情况
                    if (nums[left] < nums[right]) {
                        swapTwoNum(nums, left++, right);
                        isLesser = !isLesser;
                        continue;
                    }
                    while (nums[left] == nums[right]) {
                        right++;
                    }
                    isLesser = !isLesser;
                }
                if (right == ++left) {
                    isLesser = !isLesser;
                    continue;
                }
                swapTwoNum(nums, left, right);
            }
            System.out.println(nums);
        }

        private void swapTwoNum(int[] nums, int left, int right) {
            int temp = nums[right];
            nums[right] = nums[left];
            nums[left] = temp;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
